public class LeetCode35 {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int index = (left + right)/2;
            int mid = nums[index];
            if (mid < target){
                left = index + 1;
            }

            if (mid == target){
                return index;
            }

            if (mid > target){
                if (index > 0 && target > nums[index - 1]){
                    return index;
                }

                right = index;
            }
        }

        return left;
    }
}
